//请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。 
//
// 
// 数字 1-9 在每一行只能出现一次。 
// 数字 1-9 在每一列只能出现一次。 
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 
// 
//
// 
//
// 注意： 
//
// 
// 一个有效的数独（部分已被填充）不一定是可解的。 
// 只需要根据以上规则，验证已经填入的数字是否有效即可。 
// 空白格用 '.' 表示。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：board = 
//[["5","3",".",".","7",".",".",".","."]
//,["6",".",".","1","9","5",".",".","."]
//,[".","9","8",".",".",".",".","6","."]
//,["8",".",".",".","6",".",".",".","3"]
//,["4",".",".","8",".","3",".",".","1"]
//,["7",".",".",".","2",".",".",".","6"]
//,[".","6",".",".",".",".","2","8","."]
//,[".",".",".","4","1","9",".",".","5"]
//,[".",".",".",".","8",".",".","7","9"]]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：board = 
//[["8","3",".",".","7",".",".",".","."]
//,["6",".",".","1","9","5",".",".","."]
//,[".","9","8",".",".",".",".","6","."]
//,["8",".",".",".","6",".",".",".","3"]
//,["4",".",".","8",".","3",".",".","1"]
//,["7",".",".",".","2",".",".",".","6"]
//,[".","6",".",".",".",".","2","8","."]
//,[".",".",".","4","1","9",".",".","5"]
//,[".",".",".",".","8",".",".","7","9"]]
//输出：false
//解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无
//效的。 
//
// 
//
// 提示： 
//
// 
// board.length == 9 
// board[i].length == 9 
// board[i][j] 是一位数字（1-9）或者 '.' 
// 
// Related Topics 数组 哈希表 矩阵 👍 879 👎 0


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution0036 {

    /**
     * [0036]有效的数独 : 数的二级制模拟哈希表, 数组模拟哈希表, 关键点是推导 rowIndex、colIndex 和 areaIndex 的关系
     * <br>
     * 大多数的哈希表计数问题，都能转换为使用数组解决。
     * 虽然时间复杂度一样，但哈希表的更新和查询复杂度为均摊 O(1)，而定长数组的的更新和查询复杂度则是严格 O(1)。
     * <p>
     * 时间复杂度:O(1)
     * <br>
     * 空间复杂度:O(1)
     */
    public boolean isValidSudoku(char[][] board) {
        // 位运算: 00000000 00000000, 一个 short 可以代表 16 个位置, 0 和 1 表示状态
        short[] row = new short[9], col = new short[9], area = new short[9];
        for (int rowIndex = 0; rowIndex < 9; rowIndex++) {
            for (int colIndex = 0; colIndex < 9; colIndex++) {
                int c = board[rowIndex][colIndex];
                if (c == '.') {
                    continue;
                }
                int areaIndex = rowIndex / 3 * 3 + colIndex / 3;
                // 将`1`左移`格子中的数`位
                int num = 1 << (c - '0');
                if ((row[rowIndex] & num) != 0 || (col[colIndex] & num) != 0 || (area[areaIndex] & num) != 0) {
                    return false;
                }
                row[rowIndex] |= num;
                col[colIndex] |= num;
                area[areaIndex] |= num;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


class Test0036 {
    static char[][] board1 = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

    static char[][] board2 = {
            {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

    public static void main(String[] args) {
        System.out.println(isValidSudoku3(board1));
        System.out.println(isValidSudoku3(board2));
    }

    /**
     * 逐行判断, 逐列判断, 逐块判断, 主要推断 i 和 j 的位置
     * 第一次做, 行和列可以校验, 对于块的位置没有认真推导出来, 参考了题解, 这里记录一下
     * <p>
     * 时间复杂度:O(1)
     * <br>
     * 空间复杂度:O(1)
     */
    public static boolean first(char[][] board) {
        // 逐行判断, 逐列判断, 逐块判断
        int n = 9;
        // 逐行判断
        Set<Character> row;
        Set<Character> column;
        for (int i = 0; i < n; i++) {
            row = new HashSet<>();
            column = new HashSet<>();
            for (int j = 0; j < n; j++) {
                if (board[i][j] != '.') {
                    boolean rr = row.add(board[i][j]);
                    if (!rr) {
                        return false;
                    }
                }
                if (board[j][i] != '.') {
                    boolean lr = column.add(board[j][i]);
                    if (!lr) {
                        return false;
                    }
                }
            }
        }

        // 这里其实可以和上面一起处理, 因为是参考题解的, 单独写在这里
        HashMap<Integer, Set<Character>> blockMap = new HashMap<>(16);
        for (int i = 0; i < n; i++) {
            blockMap.put(i, new HashSet<>());
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int k = i / 3 * 3 + j / 3;
                // System.out.printf("i = %d, j = %d, k = %d%n", i, j, k);
                if (board[i][j] != '.') {
                    boolean br = blockMap.get(k).add(board[i][j]);
                    if (!br) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 逐行判断, 逐列判断, 逐块判断, 难点主要是推断 i、j 和 k 的位置 (k = i / 3 * 3 + j / 3)
     * <p>
     * 时间复杂度:O(1)
     * <br>
     * 空间复杂度:O(1)
     */
    public static boolean firstOptimization(char[][] board) {
        // 逐行判断, 逐列判断, 逐块判断
        int n = 9;
        HashMap<Integer, Set<Character>> blockMap = new HashMap<>(16);
        for (int i = 0; i < n; i++) {
            blockMap.put(i, new HashSet<>());
        }

        Set<Character> row;
        Set<Character> column;
        for (int i = 0; i < n; i++) {
            row = new HashSet<>();
            column = new HashSet<>();
            for (int j = 0; j < n; j++) {
                int k = i / 3 * 3 + j / 3;
                if (board[i][j] != '.') {
                    boolean rr = row.add(board[i][j]);
                    boolean br = blockMap.get(k).add(board[i][j]);
                    if (!(rr || br)) {
                        return false;
                    }
                }
                if (board[j][i] != '.') {
                    boolean lr = column.add(board[j][i]);
                    if (!lr) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 题解: 用哈希表的标准写法
     * <p>
     * 时间复杂度:O(1)
     * <br>
     * 空间复杂度:O(1)
     */
    public static boolean isValidSudoku1(char[][] board) {
        Map<Integer, Set<Integer>> row = new HashMap<>(), col = new HashMap<>(), area = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            row.put(i, new HashSet<>());
            col.put(i, new HashSet<>());
            area.put(i, new HashSet<>());
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') {
                    continue;
                }
                int u = c - '0';
                int idx = i / 3 * 3 + j / 3;
                if (row.get(i).contains(u) || col.get(j).contains(u) || area.get(idx).contains(u)) {
                    return false;
                }
                row.get(i).add(u);
                col.get(j).add(u);
                area.get(idx).add(u);
            }
        }
        return true;
    }

    /**
     * 题解: 用哈希表的标准写法的优化
     * <p>
     * 时间复杂度:O(1)
     * <br>
     * 空间复杂度:O(1)
     */
    public static boolean isValidSudoku1Optimization(char[][] board) {
        Set<Character> row;
        Set<Character> col;
        Map<Integer, Set<Character>> area = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            area.put(i, new HashSet<>());
        }

        for (int i = 0; i < 9; i++) {
            row = new HashSet<>();
            col = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                int k = i / 3 * 3 + j / 3;
                if (c != '.' && !(row.add(c) && area.get(k).add(c))) {
                    return false;
                }
                char c1 = board[j][i];
                if (c1 != '.' && !col.add(c1)) {
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * 题解: 数组模拟哈希表, 大多数的哈希表计数问题，都能转换为使用数组解决。
     * <br>
     * 虽然时间复杂度一样，但哈希表的更新和查询复杂度为均摊 O(1)，而定长数组的的更新和查询复杂度则是严格 O(1)。
     * <p>
     * 时间复杂度:O(1)
     * <br>
     * 空间复杂度:O(1)
     */
    public static boolean isValidSudoku2(char[][] board) {
        boolean[][] row = new boolean[9][9], col = new boolean[9][9], area = new boolean[9][9];
        for (int rowIndex = 0; rowIndex < 9; rowIndex++) {
            for (int colIndex = 0; colIndex < 9; colIndex++) {
                int c = board[rowIndex][colIndex];
                if (c == '.') {
                    continue;
                }
                int areaIndex = rowIndex / 3 * 3 + colIndex / 3;

                int num = c - '1';
                if (row[rowIndex][num] || col[colIndex][num] || area[areaIndex][num]) {
                    return false;
                }
                // 表示每一个数组中有该数字了
                row[rowIndex][num] = col[colIndex][num] = area[areaIndex][num] = true;
            }
        }
        return true;
    }

    /**
     * 题解: 使用二进制位模拟哈希表, 用位运算判断
     * <p>
     * 时间复杂度:O(1)
     * <br>
     * 空间复杂度:O(1)
     */
    public static boolean isValidSudoku3(char[][] board) {
        // 位运算: 00000000 00000000, 一个 short 可以代表 16 个位置, 0 和 1 表示状态
        short[] row = new short[9], col = new short[9], area = new short[9];
        for (int rowIndex = 0; rowIndex < 9; rowIndex++) {
            for (int colIndex = 0; colIndex < 9; colIndex++) {
                int c = board[rowIndex][colIndex];
                if (c == '.') {
                    continue;
                }
                int areaIndex = rowIndex / 3 * 3 + colIndex / 3;
                // 将`1`左移`格子中的数`位
                int num = 1 << (c - '0');
                if ((row[rowIndex] & num) != 0 || (col[colIndex] & num) != 0 || (area[areaIndex] & num) != 0) {
                    return false;
                }
                row[rowIndex] |= num;
                col[colIndex] |= num;
                area[areaIndex] |= num;
            }
        }
        return true;
    }

}